Dall'iterazione alla ricorsione: la ristrutturazione del pensiero
La ricorsione è un approccio che cambia fondamentalmente la prospettiva con cui si affrontano i problemi. Nel trattare problemi come la somma di una lista,il metodo iterativo(Listato di codice 4-2) dipende da un accumulatore esplicito theSum e dal controllo dello stato del ciclo; mentre il metodo ricorsivo si basa su una definizione matematica profonda:
$$listsum(numList) = first(numList) + listsum(rest(numList))$$
La ricorsione non è semplicemente una funzione che si chiama da sola; essa suddivide un problema complesso in sottoproblemi più piccoli della stessa struttura, e il suo nucleo risiede nella capacità di riconoscere lasimilarità autonoma。递归执行包含两个对称阶段：
- Fase di andata: tagliare ripetutamente la lista e spingere i chiamati nello stack di invocazione fino a raggiungere uncaso base(caso base).
- Fase di ritorno: partire dallo stato più semplice, tornare progressivamente verso l'alto e combinare i risultati.
Intuizione chiave
Il pensiero iterativo è come prendere un secchio e aggiungere uno per uno i numeri; il pensiero ricorsivo è invece: "Se mi dici qual è la somma dei numeri rimanenti, io aggiungerò solo il primo".